package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class WordBreakII {

	/**
	 * Input:	"catsanddog", ["cat","cats","and","sand","dog"]
		Output:	["cat sand dog"]
		Expected:	["cats and dog","cat sand dog"]
	 * @param args
	 */
	public static void main(String[] args) {
		WordBreakII wb2 = new WordBreakII();

		Set<String> dic = new HashSet<String>();
		dic.add("cat");
		dic.add("cats");
		dic.add("and");
		dic.add("sand");
		dic.add("dog");
		
		String s = "catsanddog";
		List<String> l = wb2.wordBreak(s, dic);

		List<String> l1 = new ArrayList<String>();
		l1.add("cats and dog");
		l1.add("cat sand dog");
		
		// List equals is order sensitive, could either sort or put them into a set
		Collections.sort(l1);
		Collections.sort(l);
		
		assert l1.equals(l) == true;
		
		for (String it : l) {
			System.out.println(it);
		}

	}

	public List<String> wordBreak (String s, Set<String> dict) {
		Map<String, List<String>> map = new HashMap<String, List<String>>();
		return wordBreakHelper(s, dict, map);
	}

	public List<String> wordBreakHelper(String s, Set<String> dict, Map<String, List<String>> lookup) {
		if (lookup.containsKey(s)) return lookup.get(s);

		List<String> res = new ArrayList<String>(); 
		if (s == null || s.isEmpty()) return res;

		for (int i = 1; i <= s.length(); ++i) {
			String cur = s.substring(0, i);
			if (dict.contains(cur)) {
				String sub = s.substring(i, s.length());
				if (i == s.length()) {
					res.add(cur);
				}

				List<String> r = wordBreakHelper(sub, dict, lookup);
				for (String it : r) {
					// Note the order here
					// res.add(it + " " + cur); it will be [dog sand cat, dog and cats]
					res.add(cur + " " + it);
				}
			} 
		}

		lookup.put(s, res);
		return res;
	}


}
